Lattice basis reduction methods attempt to find the shortest vector basis for a multi-dimensional lattice. These methods are important in cryptography, as well as in other applications of computational number theory.
One of the most popular methods of lattice basis reduction is the Lenstra-Lenstra-Lovasz (LLL) method, which was first described by Lenstra et al., in “Factoring Polynomials with Rational Coefficients,” Mathematische Annalen 261(4), pages 515-534 (1982), which is incorporated herein by reference. The LLL method (also referred to as the LLL algorithm) is guaranteed to produce a reduced, nearly orthogonal vector basis for a given lattice in polynomial time.
U.S. Pat. No. 7,340,606, whose disclosure is incorporated herein by reference, describes a method for producing a digital certificate using a public/private key pair. The keys are based on a pair of prime numbers p and q and a resulting modulus n that are generated by expanding a seed s. In one embodiment, the seed is expanded by building a lattice with a certain set of basis vectors, and then using the LLL algorithm to find another, shorter basis that is close to the shortest basis for the lattice. The prime number q is derived from the coordinates of the vectors in this shorter basis.